package 数据结构练习;

import java.util.ArrayList;
import java.util.List;

//普里姆算法求最小生成树
public class 普里姆算法 {
    public static void main(String[] args) {
        int[][] map = new int[6][6];
        int[][] b = new int[][]{
                {0,1,6},{0,3,5},
                {1,2,5},{2,3,7},
                {0,2,1},{1,4,3},
                {3,5,2},{2,4,5},
                {2,5,4},{4,5,6}
        };
        //初始化地图
        for(int[] x : b){
            map[x[0]][x[1]] = x[2];
            map[x[1]][x[0]] = x[2];
        }
        prim(map);
    }

    public static void prim(int[][] map){
        int[] min = new int[]{-1,-1,999999};
        List<Integer> black = new ArrayList<>();
        black.add(5);
        int result = 0;
        while (black.size()<6){
            //找到所有行中最小的
            for(int x:black){
                //找到一行中最小的
                for(int i=0;i<6;i++){
                    if(map[x][i]>0 && map[x][i]<min[2]){
                        min = new int[]{x,i,map[x][i]};
                    }
                }
            }
            //输出结果
            System.out.println(min[0]+ "->"+min[1]+" : "+min[2]);
            //清除已有的黑点和新加入的黑点的边
            for(int x:black){
                map[x][min[1]] = 0;
                map[min[1]][x] = 0;
            }
            //加入黑点
            black.add(min[1]);
            //计算结果
            result = result + min[2];
            //初始化
            min = new int[]{-1,-1,999999};
        }
        System.out.println(result);
    }
}
